package com.hdu.other.dp.gupiao;

public class lc123 {
    class Solution {
        public int maxProfit(int[] prices) {

            int len = prices.length;
            int min = prices[0];
            int[] dp1 = new int[len];
            for (int i = 1; i < len; i++)
            {
                dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
                min = Math.min(min, prices[i]);
            }
            int[] best = new int[len];
            best[0] = dp1[0] - prices[0];
            for (int i = 1; i < len; i++)
            {
                best[i] = Math.max(best[i - 1], dp1[i] - prices[i]);
            }
            int[] dp2 = new int[len];
            int ans = 0;
            for (int i = 1; i < len; i++) {
                dp2[i] = prices[i] + best[i];
                ans = Math.max(ans, dp2[i]);
            }
            return ans;
        }
    }
}
